`
https://leetcode.cn/problems/pacific-atlantic-water-flow/
`

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
  const m = heights.length, n = heights[0].length
  const canReachPO = Array.from({ length: m }, () => new Array(n).fill(false))
  const canReachAO = Array.from({ length: m }, () => new Array(n).fill(false))
  const direc = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  const isValid = (x, y) => {
    return x >= 0 && y >= 0 && x < m && y < n
  }

  const dfs = (curX, curY, ocean) => {
    if (ocean[curX][curY]) return true
    ocean[curX][curY] = true
    for (const [x, y] of direc) {
      const nextX = curX + x
      const nextY = curY + y
      // 反向寻找，只有比自己高或一样高的位置才能流过来
      if (isValid(nextX, nextY) && heights[nextX][nextY] >= heights[curX][curY]) {
        dfs(nextX, nextY, ocean)
      }
    }
  }

  for (let i = 0; i < n; i++) {
    // 遍历横向第一排
    dfs(0, i, canReachPO)
    // 遍历横向最后一排
    dfs(m - 1, i, canReachAO)
  }
  for (let i = 0; i < m; i++) {
    // 遍历竖向第一排
    dfs(i, 0, canReachPO)
    // 遍历竖向最后一排
    dfs(i, n - 1, canReachAO)
  }

  const res = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (canReachAO[i][j] && canReachPO[i][j]) {
        res.push([i, j])
      }
    }
  }
  return res
};